#include<iostream>
#include<string>
using namespace std;


namespace key_val
{
	template<class K, class V> //key和value
	//node
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _val;

		BSTreeNode(const K& key, const V& val)
			:_left(nullptr),
			_right(nullptr),
			_key(key),
			 _val(val)
		{}
	};

	template<class K,class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}
			
			//找到适合插入的位置
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) 
			{
				parent = cur;  //更新parent
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key) //更新parent
				{
					cur = cur->_right;
				}
				else
					return false;
			}

			//准备插入  插入点一定是空结点
			cur = new Node(key, value);

			//判断插入父亲的左还是右
			if (parent->_key > key) parent->_left = cur;
			else parent->_right = cur;

			//插入成功
			return true; 

		}
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
					cur = cur->_right;
				else if (cur->_key > key)
					cur = cur->_left;  
				else
					return cur;
			}

			return nullptr; //没找到，返回空指针
		}


		bool Erase(const K& key)
		{
			//1.k的左为空
			//2.k的右为空
			//3.k左右都存在，替换删除

			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				parent = cur; //更新父亲
				if (cur->_key < key) cur = cur->_right;
				else if (cur->_key > key) cur = cur->_left;

				//找到了
				else
				{
					//1.左为空
					if (cur->_left == nullptr)
					{

						//删除点为根
						if (cur == _root) _root = cur->_right;

						//判断是父亲的左、右链接
						if (parent->_right == cur)  //右链接
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}

					}

					//2.右为空
					else if (cur->_right == nullptr)
					{
						//删除点为根
						if (cur == _root) _root = cur->_left;

						//判断是父亲的左、右链接
						if (parent->_right == cur)  //右链接
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					//3.替换
					else
					{
						//找右数的最小 右子树的最左边元素
						Node* pminright = cur;
						Node* minright = cur->_right;
						
						//找到左树空就找到了
						while (minright->_left)
						{
							pminright = minright;  //保存父亲结点
							minright = minright->_right;	
						}

						cur->_key = minright->_key;  //交换

						//判断是父亲的左子树还是右子树要被删除
						if (pminright->_left ==minright )
							pminright->_left = minright->_right;
						else 
							pminright->_right= minright->_right;
					}



				}
			}
			delete(cur);
			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_val << endl;
			_InOrder(root->_right);

		}

	private:
		Node* _root = nullptr;
	
	
	};


	//void TestBSTree()
	//{
	//	BSTree<string, string> dict;
	//	dict.Insert("insert", "插入");
	//	dict.Insert("erase", "删除");
	//	dict.Insert("left", "左边");
	//	dict.Insert("string", "字符串");
	//	dict.Erase("insert");
	//	dict.InOrder();
	//	dict.Erase("erase");
	//	dict.InOrder();
	//}


	void TestBSTree()
	{
		//BSTree<string, string> dict;
		//dict.Insert("insert", "插入");
		//dict.Insert("erase", "删除");
		//dict.Insert("left", "左边");
		//dict.Insert("string", "字符串");

		//string str;
		//while (cin >> str)
		//{
		//	auto ret = dict.Find(str);
		//	if (ret)
		//	{
		//		cout << str << ":" << ret->_val << endl;
		//	}
		//	else
		//	{
		//		cout << "单词拼写错误" << endl;
		//	}
		//}

		string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
		// 统计水果出现的次
		BSTree<string, int> countTree;
		for (auto str : strs)
		{
			auto ret = countTree.Find(str);
			if (ret == NULL)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_val++;
			}
		}
		countTree.InOrder();
	}

}



